package argos.util.graph;

import java.util.ArrayList;
import java.util.List;

public class Graph {
	
	public static List<Node> findCircle(List<?> nodes) {
		List<Node> path = new ArrayList<Node>();
		List<Node> verified = new ArrayList<Node>();
		
		for(int i = 0; i < nodes.size(); i++) {
			path.clear();
			Node node = (Node) nodes.get(i);
			if(findCircle(node, node, path, verified)) {
				return path;
			}
		}
		
		return null;
	}
	
	private static boolean findCircle(Node start, Node current, List<Node> path, List<Node> verified) {
		if(verified.contains(current)) {
			return false;
		}
		else if(path.contains(current)) {
			return true;
		}
		else {
			path.add(current);
			for(Node node : current.getThisDependsOn()) {
				if(findCircle(start, node, path, verified)) {
					return true;
				}
			}
			verified.add(current);
			path.remove(path.size() - 1);
			return false;
		}
	}
}
